This invention relates to a routing apparatus that uses a CAM (Content Addressable Memory) when routing is performed in a network such as the Internet or ATM network. More particularly, the invention relates to a routing apparatus for obtaining routing data, which conforms to the destination address of a packet that arrives from a line, from a CAM, adding the routing data onto the packet, and switching the packet based upon this routing data to send the packet to a prescribed line.
The processing speeds of routers and ATM switches is increasing with the explosive spread of the Internet and ATM networks. Owing to lines packed in higher densities, tables for searching data (routing data) necessary for routing and switching are increasing in capacity.
Methods of searching routing data rely upon conventional processing technology using a CAM. However, an increase in the capacity CAMs is accompanied by the need for a large number of CAMs if the CAMs are of the usual capacity. It is difficult to package all the CAMs on an ordinary LSI chip. Therefore, a CAM of large capacity is recently available on the market as a special-purpose LSI chip.
FIG. 15 is a block diagram illustrating the general structure of a router according to the prior art. This will be used to describe an overview of a search method using a CAM in an ordinary router. The router has a main controller (CPU) 1, a switch 2 and line cards 31˜3n, 41˜4n provided between lines and the switch 2. Data transmission over a line generally is transmission using POS (Packet over SONET or Packet over SONET). With POS, an IP packet is mapped to an SDH or SONET payload and then transmitted. Line terminators (not shown) separate IP packets from the POS lines and input the IP packets to line cards 31˜3n. A packet processor 3a in each of the line cards 31˜3n extracts the destination address of the IP packet, acquires routing data conforming to the destination address from a CAM 3b, adds the routing address onto the packet and inputs the packet to the switch 2. On the basis of routing data attached to packets which enter from the line cards 31˜3n, the switch 2 switches these packets and inputs them to different line cards 41˜4n. Packet processors in the line cards 31˜3n remove the routing data from the packets, subsequently map the packets to the payloads of SDH or SONET frames and send the packets to POS lines.
FIG. 16 is a block diagram of a line card illustrating the CAM 3b as being separated into a CAM LSI chip 3b1 and an associative memory 3b2. FIG. 17 is a flowchart of a CAM search. A key-data memory (not shown) of the CAM LSI chip 3b1 stores key data conforming to a number of destination addresses, and the associative memory 3b2 stores routing data. The IP header of an IP packet has a destination address DA (destination address=IP address). When the IP packet enters the packet processor 3a of any of the line cards 31˜3n (step 101), therefore, the destination address DA is extracted (step 102) from the IP packet that has entered and the destination address is transferred as key data to the CAM 3b, which has a conversion table, in advance. The CAM LSI chip 3b1 of the CAM 3b checks to determine whether an IP address corresponding to this key data exists in the key-data memory. If the IP address exists, the CAM LSI chip 3b1 converts this key data to an address of the associative memory 3b2 and sends the latter to the associative memory 3b2 (step 103). The associative memory 3b2, which is constituted by a RAM, outputs preset associative data, e.g., a highway number HW-No. that is necessary for switching, based upon the entered address. Immediately before outputting the IP packet, the packet processor 3a adds this highway number HW-No. onto the packet and then inputs the packet to the switch 2. The latter performs routing (step 104) using the highway number HW-No.
FIG. 18 is a block diagram showing the details of the conventional router. Components in FIG. 18 identical with those shown in FIGS. 15 to 17 are designated by like reference characters. Main controllers 1, 1′ are redundant in order to improve reliability and are identically constructed. Specifically, the main controllers 1, 1′ respectively include: (1) main processors (MPU) 1a, 1a′; (2) main memories (MM) 1b, 1b′; (3) cache memories (not shown); (4) MPU bus conversion bridges 1c, 1c′ for connecting various devices such as input/output units and a CAM to the MPU; (5) output-port search CAMs 1d, 1d′ for when the main controller performs communication with the neighboring router; (6) Ethernet switching hubs 1e, 1e′ for transferring routing tables created by the main controller to each of the line cards 31˜3n via the switch 2 on separate lines; and (7) MPU bus conversion bridges 1f, 1f′ for sending the MPU packets addressed to this router that arrive from the line cards via the switch.
The line cards 31˜3n accommodate various lines such as SONET or SDH lines and are identically constructed. The speeds of the lines accommodated by each line card are the same but the line speeds differ from one card to another. The packet processor 3a (1) extracts the destination address DA of a packet that arrives via a POS line or the like and sends this destination address DA to the CAM as key data for searching routing data; (2) adds the routing data (highway number HW-No.) onto the packet and sends the packet to the switch; and (3) removes routing data from a switched packet and sends the packet to a line. The CAM 3b has the CAM LSI chip and associative memory (see FIG. 16) and obtains routing data (highway number HW-No.) from the destination address DA that has entered as key data. The CAM 3b executes the reverse of this operation as well. A LAN controller (LANC) 3c receives routing data by communicating with switching hubs 1e, 1e′ of the main controllers. A local MPU 3d controls the LAN controller 3c and controls the configuration internally of the line card.
The switch 2 controls the exchange of packets between the line cards and the main controllers 1, 1′ and controls the exchange of packets between the line cards.
FIG. 19 is an explanatory view illustrating the flow of packets in the conventional router.
1) A data packet that has entered from a POS line is separated into packets by the input section of a line card 3. It should be noted that PPP in FIG. 19 signifies Point-to-Point Protocol.
2) On the basis of the IP destination address DA in the packet header, the packet processor 3a searches the CAM 3b for a highway number HW-No. and other necessary information (QOS information, filtering information, etc.), adds the HW-No. and other information onto the packet (the payload portion thereof) and transfers the packet to the switch 2.
3) The switch 2 switches the packet based upon the routing data HW-No. and other information and inputs the packet to a line card 4 on the egress side. A packet processor 4a in the line card 4 removes the routing data HW-No. and other information from the packet that enters from the switch.
4) The packet processor 4a finally maps the packet to the payload of an SDH or SONET frame and sends the packet to a POS line. This completes routing processing in its entirety.
FIG. 20 is a diagram illustrating the internal structure of the CAM LSI chip. The CAM LSI 3b1 has an address decoder 5a, a memory array 5b, an index register 5c, a mask register 5d, a response register 5e and a priority encoder 5f. 
The address decoder 5a decodes address data and stores separately input key data at a prescribed address of the memory array 5b or reads key data out of the memory array 5b and outputs the same. The memory array 5b stores key data conforming to the number of destination addresses, and the index register 5c stores key data desired to be searched (i.e., search key data), e.g., key data conforming to the destination address of a packet received from a POS line. The mask register 5d specifies the bit position to be masked in the search key data (masking is performed by logical “1”). The response register 5e stores (1) the result of performing matching (comparison) between key data, which has been stored in the memory array 5b, and search key data or (2) the result of performing matching between key data, which has been stored in the memory array 5b, and the non-masked portion of the search key data. The priority encoder 5f generates an address of the associative memory 3b2 based upon the result of matching from the response register 5e. The associative memory 3b2 outputs associative data (routing data and other information) from the entered address.
The key data shown in FIG. 20 is indicated as being 8-bit data for the sake of explanation; 32-bit data, etc., is employed in actuality. Further, the memory array 5b is illustrated as storing eight items of key data, though the memory array 5b actually has enough capacity to store a great many items of key data. Further, the memory array 5b within the CAM is so adapted that bit width can be varied in dependence upon the application of the CAM search, and the memory array has a register (not shown) for changing the configuration of the memory array. With regard to the associative memory 3b2, however, the bit width of the associative addresses and associative data is fixed at the hardware-design stage.
The following problems arise with the conventional routing apparatus (router) using the CAM:
1) High Cost of the CAM LSI Chip
The number of CAM entries is increasing as use of the Internet becomes more widespread. The number of entries that can be processed per CAM LSI chip is 64,000 at most if it is assumed that 36 bits per entry are required. Here 36 is the total of 32 bits required as the destination address in IP-V4 (IP Version 4) and four bits serving as control bits.
2) High Mounting Surface Occupancy of CMI LSI Chips
If it is assumed that 15 CAM LSI chips (4×4 cm in size) are required to be mounted, a high mounting surface occupancy is the result. This requires that the line card have a complicated structure, such as a two-tier structure.
3) Transfer Time of Routing Tables
It is necessary to transfer routing tables to each of the line cards from the main processor of the main controller that performs centralized administration of routing tables. For example, when the system is started up, it is necessary to transfer a routing table from the main processor of the main controller to the CAM mounted on each line card. As a consequence, system start-up takes considerable time and so does recovery at the time of failure.
4) Changing Bit Width of Associative Data
The construction of a CAM is such that the associative memory constituted by a RAM is externally mounted on the CAM LSI. Consequently, if key data is changed from IP-V4 to IP-V6 (4 bytes to 16 bytes), it becomes necessary to change the circuit configuration of the hardware and the line card must be redesigned.
5) Multiple Hits in Key Data
Since the conventional CAM does not possess a statistical processing function, the CAM cannot execute statistical processing at the time of multiple hits, namely when there are multiple items of entry key data for search key data. Consequently, it is required that the MPU of the main controller calculate statistical information by program processing using the main memory (MM), which results in a large head of the MPU.
6) Relationship Between Line Speed and CAM
In the conventional router, a CAM is mounted on a line card and the line card accommodates a plurality of lines of the same speed (an example of mounting is OC-12 lines×4). The reason for this is that in an arrangement in which a line card accommodates lines having different speeds, costs rise because all of the line cards will require a costly CAM of maximal speed. However, with the router of the conventional arrangement in which each card accommodates lines having the same speed, it is required to provide a line card that conforms to each line speed. Depending upon the network, there will be line cards that cannot be used and situations will arise in which the lines accommodated by line cards are too few in number. In other words, the conventional routing apparatus is such that the line cards have a poor line accommodating efficiency, and the apparatus is high is cost.